package _18_剑指OfferII;

public class _118_剑指OfferII多余的边 {

    int[] parent;

    // 并查集寻找
    public int[] findRedundantConnection(int[][] edges) {
        int len = edges.length;
        parent = new int[len + 1];
        for (int i = 0; i <= len; ++i) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            if (find(from) != find(to)) union(from, to);
            else return edge;
        }
        return new int[0];
    }

    private int find(int index) {
        return parent[index] == index? index: find(parent[index]);
    }

    private void union(int index1, int index2) {
        // 右合并左
        parent[find(index2)] = parent[index1];
    }
}
